﻿#include <iostream>
#include "BinaryTree.h"

typedef struct {
    BinaryTreeNode* head;
    BinaryTreeNode* end;
}ToDoubleLinkedListData;

static ToDoubleLinkedListData recur(BinaryTreeNode* head)
{
    ToDoubleLinkedListData data;
    data.head = nullptr;
    data.end = nullptr;
    if (!head) return data;

    auto leftData = recur(head->left);
    auto rightData = recur(head->right);
    if (!leftData.head)
    {
        data.head = head;
    }
    else
    {
        leftData.end->right = head;
        head->left = leftData.end;
        data.head = leftData.head;
    }

    if (!rightData.head)
    {
        data.end = head;
    }
    else
    {
        rightData.head->left = head;
        head->right = rightData.head;
        data.end = rightData.end;
    }

    return data;
}

// 双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left，next认为是right的话。
// 给定一个搜索二叉树的头结点head，请转化为一条有序的双向链表，并返回链表的头节点。
//
// 比如:
//   5
//  / \
// 3   7
//
// 转化为: 3↔5↔7
//
// 思路:
//	采用树型dp思路，分别将左子树和右子树转化为双向链表，然后，左子树链表的尾节点与head相连，
//	head再与右子树链表的头节点相连
int main_ToDoubleLinkedList()
{
    auto head = new BinaryTreeNode(11);
    head->left = new BinaryTreeNode(7);
    head->left->left = new BinaryTreeNode(3);
    head->left->right = new BinaryTreeNode(9);
    head->right = new BinaryTreeNode(15);
    head->right->left = new BinaryTreeNode(12);
    head->right->right = new BinaryTreeNode(18);

    auto data = recur(head);
    auto linkedHead = data.head;
    while (linkedHead)
    {
        auto next = linkedHead->right;
        printf("%d(0x%08x)<->", linkedHead->getValue(), linkedHead);
        delete(linkedHead);
        linkedHead = next;
    }

    printf("\n");
    return 0;
}